Tutoriel HsIndex 5 - Traitement des données

Date de publication : 06/02/2019 22:52:00

Regroupement des numéros des pages

Les entrées possédant le même nom doivent être regroupées et leurs numéros de pages ajoutés en liste afin de générer correctement l'index.

Pour cela, on crée une fonction :

concatPagesItems :: [IndexItem] 
                 -> [IndexItem]
concatPagesItems []                                   = []
concatPagesItems lst@(IndexItem nam equ pag sub : xs) = IndexItem nam equ pages subentries : concatPagesItems a
    where
        (p, a)     = partition (\e -> itemName e == nam) xs
        pages      = nub $ sort $ concat $ pag : map itemPages p
        subentries = concatPagesSubItems $ concat $ sub : map itemContent p

Pour chaque élément de la liste, on partitionne les éléments contenant le même nom avec la fonction partition. Cette fonction fonctionne comme filter mais en retournant les résultats conformes et non-conformes au prédicat.

On concatène ensuite les numéros de pages avec la fonction concat, on les trie par ordre croissant avec sort et on élimine les doublons avec nub.

Pour les sous-entrées, on appelle la fonction qui leur est dédiée concatPagesSubItems qui fonctionne globalement comme concatPagesItems.

On crée un nouvel élément IndexItem contenant les sous-entrées triées et les numéros de pages concaténés et on appelle la fonction concatPagesItems de façon récursive avec les éléments ayant un nom différent.

On n'oublie pas de créer une empreinte liste vide (concatPagesItems [] = []) pour éviter une erreur de type :

*** Exception: Functions.hs:125:1-49: Non-exhaustive patterns in function concatPagesItems

Note : Pour se prémunir contre ce genre de problème, on peut passer l'option -Wincomplete-patterns au compilateur pour l'obliger à rechercher les empreintes incomplètes :

Functions.hs:125:1: warning: [-Wincomplete-patterns]
    Pattern match(es) are non-exhaustive
    In an equation for ‘concatPagesItems’: Patterns not matched: []

Regroupement des entrées

Les entrées sont regroupées comme suit:

• Les sections contiennent les mots appartenant à la même section et avec le même premier caractère.

• Les sous-sections contiennent les mots avec les mêmes deux premiers caractères.

Note : Le fonctionnement de cette fonction implique que la liste d'entrées de base soit triées. Dans le cas contraire, la fonction retournera des résultats incohérents.

Fonction principale

On crée une fonction splitIndex

splitIndex :: IndexStyle  -- ^ The style of the 'Index'.
           -> [IndexItem] -- ^ List of 'IndexItem's to sort in a 'Index'.
           -> Index       -- ^ The final index.
splitIndex style []           = []
splitIndex style lst@(x : xs) = if null d
    then splitIndex style f
    else IndexSection tit (splitIndex' style d) : splitIndex style f
    where
        (d, f) = span (\c -> areItemsEqual (itemEqui c) (itemEqui x)) lst
        tit    = showHeading1 style (itemEqui (head d))

La fonction recherche tous les éléments consécutifs appartenant à la même section et avec la même première lettre. Cette recherche est effectuée avec la fonction span et du test effectué par la fonction areItemsEqual (voir plus loin).

Une section IndexSection est créée avec le titre de section correspondant (fonction showHeading1) et les sous-sections regroupées de la même manière avec la fonction splitIndex'.

Le reste de la liste est généré en appelant la fonction splitIndex avec les autres éléments.

Ici aussi, on n'oublie pas de créer une empreinte pour la liste vide.

Tests d'égalités

Pour tester l'égalité entre deux éléments, on utilise une fonction intermédiaire prenant en compte la section et le nom équivalent.

areItemsEqual (Letters, a) (Letters, b) = take 1 a == take 1 b
areItemsEqual (Numbers, a) (Numbers, b) = True
areItemsEqual (Symbols, a) (Symbols, b) = True
areItemsEqual _            _            = False

areItemsEqual' (Letters, a) (Letters, b) = take 2 a == take 2 b
areItemsEqual' (Numbers, a) (Numbers, b) = take 1 a == take 1 b
areItemsEqual' (Symbols, a) (Symbols, b) = take 1 a == take 1 b
areItemsEqual' _            _            = False

Tri des entrées

Haskell possède une fonction de tri sort :: [a] -> [a], mais cette fonction n'est pas suffisamment évolué pour répondre au besoin du programme. En effet, s'il est possible donner un ordre spécifique à un type donné en définissant la fonction compare de la classe Ordering, cet ordre sera codé en dur et ne pourra pas être modifié pendant l'exécution du programme. Or il est justement nécessaire de pouvoir modifier cet ordre de manière interactive.

On utilisera donc pour le tri la fonction sortBy :: (a -> a -> Ordering) -> [a] -> [a] qui permet de passer une fonction de comparaison définie par l'utilisateur.

Cette fonction de comparaison sera du type a -> a -> Ordering et devra avoir comme arguments les deux éléments à comparer.

Comparaison des éléments entre eux

On utilise une fonction spécifique pour comparer deux éléments en fonction de leur section et de leur nom équivalent.

compareBySection :: LangDef           -- ^ The list of 'Char's for each section.
                 -> (Section, String) -- ^ The first item to compareBySectionre.
                 -> (Section, String) -- ^ The second index to compareBySectionre.
                 -> Ordering          -- ^ The 'Ordering'.
compareBySection cha (seca, stra) (secb, strb) = case (ind_a, ind_b) of
    (Just ia, Just ib) | ia == ib  -> compareByString (genListChar cha) stra strb
                       | ia < ib   -> LT
                       | otherwise -> GT
        where
            recu
                | seca == Letters = compareByString (lstLetters cha) stra strb
                | seca == Numbers = compareByString (lstNumbers cha) stra strb
                | seca == Symbols = case lstSymbols cha of
                    Nothing -> EQ -- error "No list of symbols defined"
                    Just ch -> compareByString ch stra strb
    (Nothing, _      ) -> error ""
    (_      , Nothing) -> error ""
    where
        ind_a = elemIndex seca (lstSecOrder cha)
        ind_b = elemIndex secb (lstSecOrder cha)

1. Cette fonction commence par trouver la position de la section de chaque élément dans l'ordre définit dans le type LangDef en utilisant la fonction elemIndex.

2. On compare ces positions entre elles:

   1. Si ces positions sont trouvées (Just) et égales (même section), on compare les noms équivalents avec la fonction dédiée compareByString.

   2. Si ces positions sont différentes, on renvoie un constructeur LT ou GT du type Ordering permettant de définir une relation d'ordre (Voir module Data.Ord).

On utilise ensuite une fonction permettant de comparer les chaînes de caractères:

compareByString :: String   -- ^ The list of Char's giving the order.
                -> String   -- ^ The first 'String' to compare.
                -> String   -- ^ The second 'String' to compare.
                -> Ordering -- ^ The 'Ordering' result.
compareByString ordlst []       []       = EQ
compareByString ordlst []       (b : bx) = LT -- GT
compareByString ordlst (a : ax) []       = GT -- LT
compareByString ordlst (a : ax) (b : bx) = case (ind_a, ind_b) of
    (Just ia, Just ib) | ia == ib  -> compareByString ordlst ax bx
                       | ia < ib   -> LT
                       | otherwise -> GT
    (Nothing, Nothing) -> compareByString ordlst ax bx
    (Nothing, _      ) -> LT
    (_      , Nothing) -> GT
    where
        ind_a = elemIndex a ordlst
        ind_b = elemIndex b ordlst

1. Cette fonction commence par trouver la position du caractère a et b de chaque élément dans l'ordre définis dans le type LangDef en utilisant la fonction elemIndex.

2. On compare ces positions entre elles:

   1. Si ces positions sont trouvées (Just) et sont égales (même caractère), on compare les caractères suivant en appelant la fonction compareByString de manière récursive avec le reste des chaînes de caractère ax et bx

   2. Si ces positions sont différentes, on renvoie un constructeur LT ou GT du type Ordering permettant de définir une relation d'ordre (Voir module Data.Ord).

   3. Si les positions ne sont pas trouvées (Nothing) (caractère introuvable dans la liste) on appelle la fonction compareByString de manière récursive avec le reste des chaînes de caractère ax et bx.

   4. Pour les cas ou on arriverait en bout d'une des chaînes, on crée deux empreintes listes vides ([]) qui permettent de renvoyer un type Ordering.

Classement des éléments

Pour trier une liste d'éléments IndexItem, on crée une fonction :

sortItems :: LangDef
          -> [IndexItem]
          -> [IndexItem]
sortItems cha lst = sortBy (\a b -> compareBySection cha (itemEqui a) (itemEqui b)) nlst
    where nlst = map (\itm -> itm { itemContent = sortSubItems cha (itemContent itm) }) lst

Cette fonction appelle la fonction sortBy avec la fonction de comparaison compareBySection avec une liste d'éléments dont les sous-éléments ont été eux-mêmes triés avec une fonction sortSubItems qui leur est dédiée.

sortSubItems :: LangDef
             -> [IndexSubItem]
             -> [IndexSubItem]
sortSubItems cha lst = sortBy (\a b -> compareBySection cha (subItemEqui a) (subItemEqui b)) nlst
    where nlst = map (\itm -> itm { subItemContent = sortSubSubItems cha (subItemContent itm) }) lst


sortSubSubItems :: LangDef
                -> [IndexSubSubItem]
                -> [IndexSubSubItem]
sortSubSubItems cha lst = sortBy (\a b -> compareBySection cha (subSubItemEqui a) (subSubItemEqui b)) lst

Et voila pour le traitement des données de l'index.